Evolution of Three-Dimensional Cellular Automata: Genetic Algorithms
See
One-Dimensional Cellular Automata
for a basic introduction to cellular automata.
Introduction
Like their one and two-dimensional counterparts, three-dimensional cellular
automata are specified by an initial state and a set of transition rules
used to transform the state of each cell in each time step. The following
presentation details the use of genetic algorithms to automatically generate
the initial state and transition rules which arrive at a pre-specified
goal state. Better understanding of cellular automata configuration could
lead to developments in many diverse fields, from industrial design
[Bentley and Corne, 2002]
and
nanotech computer architecture
[Drexler, 1992]
to morphology and embryology in biology
[Thompson, 1942]
[Stewart, 1998].
Goal State
Our three-dimensional cellular automata consists of a 40x40x40 cube of cells.
In each time step the new value of a cell is computed based on the current
value of the cell and the current values of its 26 direct neighbors. The
system is initialized with some portion of the 27 cell cube centered at
(21,21,21) turned on. The goal is to have the 27 cell cube centered at
(31,31,31) be turned on (and all other cells off)
10 time steps later. The obvious (to us) solution
is to initialize a cube at (21,21,21) and move it (+1,+1,+1) in each time
step to arrive at (31,31,31) on time step 10.
| Start | End |
 |  |
While this particular problem is trivial, the solution search space is much
too large for random search. A genetic algorithm that can solve this problem
should also be able to solve problems in cellular automata configuration
whose solutions are non-obvious to humans.
See also presentation on search.
Genotype
Each possible solution to the problem is represented as a 54-digit string,
where each digit can take on 2, 3 or 5 values.
The first 27 digits represent the initial state of the 27 cells of the
cube centered at (21,21,21). The second 27 digits represent the
transition rule applied to the cells. The transition rule forms an
equation:
next_state[x][y][z] = transition_rule[0] * current_state[x][y][z-1] +
transition_rule[1] * current_state[x-1][y][z-1] +
transition_rule[2] * current_state[x+1][y][z-1] + ... +
transition_rule[26] * current_state[x][y][z];
if(next_state < 0) next_state = 0; if(next_state > max) next_state = max
Three different cellular automata were tested:
- Two-Valued (Binary)
- Cells take on values 0 [black], 1 [white]
- Transition rule digits 0 or 1
- 2^54 = 18,014,398,509,481,984 possible genomes in search space
- Three-Valued
- Cells take on values 0 [black], 1 [white], 2 [red]
- Transition rule digits -1, 0, 1
- 3^54 = 58,149,737,003,040,059,690,390,169 possible genomes in search space
- Five-Valued
- Cells take on values 0 [black], 1 [white], 2 [red], 3 [green], 4 [blue]
- Transition rule digits -2, -1, 0, 1, 2
- 5^54 = 55,511,151,231,257,827,021,181,583,404,541,015,625 possible genomes in search space
Evaluation Function
Two different evaluation functions were used to score the generated solutions.
Each applied a positive value for each "on" cell inside the target region and
a negative value for each "on" cell outside the target region. Here "on"
meant a value > 0, so no distinction was made between 2,3,4 [red,green,blue]
in the three and five-valued automata.
- Old Evaluation Function
- +40 for each "on" cell inside the target region
- -1 for each "on" cell anywhere (so target cells are net +39)
- Maximum score: 1053
- New Evaluation Function
- +100 for each "on" cell inside the target region
- -1 per step of x,y,z distance from (31,31,31) for each "on" cell anywhere (so target cells can be net +100 to +97)
- Maximum score: 2646
The Genetic Algorithm
A population of 100 individuals was created with random values for each digit.
The evaluation function was applied to determine the
fitness of each individual.
Pairs of individuals were randomly selected for reproduction. Their
probability of selection was determined by their fitness. The selected
individuals were both copied unchanged into the next generation and
crossed over. The crossed over copies also each had a single random
point mutation applied. In each generation the most fit individual was
also preserved, guaranteeing the maximum fitness of the population
could never fall.
Results
The genetic algorithm was run six times, applying both the old and
new evaluation functions to the two, three, and five-valued automata.
The results are graphed separately:
Screen shots were also captured for generations 0,25,50,100,150,200,250
(skipping generations with unchanged fitness score)
Of the six runs only one, the two-valued with new evaluation function run,
reached the goal within 260 generations. This test was re-run using a
different seed value
for the random number generator. The configuration succeeded again,
with nearly identical results. See the graph comparing the results:
Of the rest of the results I would consider those for three-valued
(both old and new eval) to be acceptable. And noting the larger search spaces,
all runs may eventually reach the goal given sufficient generations / run time.
Conclusions
Genetic algorithms can be successfully applied to find useful cellular
automata configurations within an enormous search space. Further investigation
of the relationship between evaluation functions and numbers of allowed cell
values is needed.
This work is continued using the Adaptive Culture Model in
Evolution of Three-Dimensional Cellular
Automata: Adaptive Culture Model.
Implementation Notes
Genetic algorithm and cellular automata custom implemented in C using gcc
and OpenGL on Linux. Six simultaneous runs of 260 generations took 34 hours on
a 700 MHz Athlon. Graphics by nvidia GeForce2, graphs by gnuplot, screen shots
by the GIMP.
References
Bentley, Peter J. and David W. Corne, eds., 2002. Creative Evolutionary Systems.
Drexler, Eric K., 1992. Nanosystems: Molecular Machinery, Manufacturing, and Computation.
Stewart, Ian, 1998. Life's Other Secret: The New Mathematics of the Living World.
Thompson, D'Arcy Wentworth, 1942. On Growth and Form.